home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / MacHaskell 2.2 / progs / lib / hbc / QSort.hs < prev    next >
Encoding:
Text File  |  1994-09-27  |  1.2 KB  |  48 lines  |  [TEXT/YHS2]
  1. {-
  2.    This module implements a sort function using a variation on
  3.    quicksort.  It is stable, uses no concatenation and compares
  4.    only with <=.
  5.   
  6.    sortLe sorts with a given predicate
  7.    sort   uses the <= method
  8.   
  9.    Author: Lennart Augustsson
  10. -}
  11.  
  12. module QSort(sortLe, sort) where
  13. sortLe :: (a -> a -> Bool) -> [a] -> [a]
  14. sortLe le l = qsort le   l []
  15.  
  16. sort :: (Ord a) => [a] -> [a]
  17. sort      l = qsort (<=) l []
  18.  
  19. -- qsort is stable and does not concatenate.
  20. qsort le []     r = r
  21. qsort le [x]    r = x:r
  22. qsort le (x:xs) r = qpart le x xs [] [] r
  23.  
  24. -- qpart partitions and sorts the sublists
  25. qpart le x [] rlt rge r =
  26.     -- rlt and rge are in reverse order and must be sorted with an
  27.     -- anti-stable sorting
  28.     rqsort le rlt (x:rqsort le rge r)
  29. qpart le x (y:ys) rlt rge r =
  30.     if le x y then
  31.     qpart le x ys rlt (y:rge) r
  32.     else
  33.     qpart le x ys (y:rlt) rge r
  34.  
  35. -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
  36. rqsort le []     r = r
  37. rqsort le [x]    r = x:r
  38. rqsort le (x:xs) r = rqpart le x xs [] [] r
  39.  
  40. rqpart le x [] rle rgt r =
  41.     qsort le rle (x:qsort le rgt r)
  42. rqpart le x (y:ys) rle rgt r =
  43.     if le y x then
  44.     rqpart le x ys (y:rle) rgt r
  45.     else
  46.     rqpart le x ys rle (y:rgt) r
  47.  
  48.